package com.otherTest.datastructure.tree;

import org.junit.Test;

import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * 红黑树
 * 全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)
 * 红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。
 * Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的
 * 特征
 * 1:根节点为黑色
 * 2:叶子节点也为黑色
 * 3:每个节点非黑即红
 * 4:如果一个节点是红色的,那么它的子节点必须都为黑色
 * 5:每个节点下的子孙节点包含同样数目的黑色节点
 * 注意
 * 1:因为红黑树也是二叉树所以每个节点的值都大于等于其左子节点的所有子孙节点，小于等于右子节点的所有子孙节点
 *
 * @author Conceit
 * @since 1.0.0, 2017/8/1
 */
public class RBTree {

    @Test
    public void test() {
        Map<String, Integer> maps = new TreeMap<>();
        Set<String> set = new TreeSet<>();
    }

    /**
     * 插入
     */
    public void insert() {

    }

    /**
     * 删除
     */
    public void delete() {

    }

    /**
     * 查询
     */
    public void select() {

    }

    /**
     * 左旋
     */
    public void leftRotate() {

    }

    /**
     * 右旋
     */
    public void rightRotate() {

    }

    /**
     * 反转
     */
    public void revaseInversion() {

    }


}
